TIS Chapter 5 revised
MultiversionとReads-From Relation
Preface: Reads-From Relation
$ RF(s) := \{(t_i, x, t_j)| an\ r_j(x)\ reads\ x\ from\ a\ w_i(x)\}
Preface: CSR的にConflict Graphを作ることはMultiversionでは出来ない
添字を単純にdropするとReads-Fromが変わる
ex5.5: Serial Multiversion scheduleであっても，versionをdropするとRFがserialと一致するとは限らない
Reads-From Relationの考え方からやりなおす必要がある
TIS Chapter 3で見たやり方では，Readとはつまりreads the last writesだったけどそうじゃないから つまり$ r_1(x_0) but there is exist$ x_1みたいなことがある
これは特定のプロトコルの話ではなく，添字があるとこうなるという話
Multiversion View Serializability(MVSR)
そして重要な以下のcriterionが導かれる: (しかしexample-driven discussionと言っていて，真にそうかは分からないなあ)
Definition 5.6 Multiversion View Serializability
Let$ mbe a multiversion history.
Then$ mis called multiversion view serializable if there exists a serial monoversion history $ m' for the same set of transactions such that $ m=_v m'
簡単に言うとView Equivalentなmonoversion serial historyがあれば，MVSRに含まれる．
これは当然CSRも含む．View E ⊃ Conflict E だし, Multiversion History ⊃ Monoversion Historyだから．
Multiversion scheduleはMonoversion Historyにcastできることを考えれば，自明．
Testing Membership in MVSR
まず，当たり前だが
Theorem 5.1
$ VSR \subset MVSR
VSRはmonoversionにおけるcriterionである
monoversion historyが monoversion serial historyとView Equivalentであるかを検証する．
対してMVSRは入力がMultiversion Historyであるためこちらのほうが広い．
ということはVSRはMVSRに制約を加えたものであるとわかる
VSRの計算量がNP-Completeであるから，MVSRはそれと同等以上であることもわかる
Conflict Graph for MVSR
MVSRでもConflict Graphを使える
ただしMonoversionとは異なる定義をする
このGraph定義はProtocolを考える上での基底理論であるから重要
では，MultiversionにおけるConflict Graphについて:
MVSRでは$ w-rのedgeのみを考慮する
それはなぜか？という点は以下しか書いていない
due to the fact that only conflicts of the form $ (w_i(x_i), r_j(x_i)) can still occur
Theorem 5.3
For any two multiversion schedules $ m and $ m', $ m \approx_v m' implies $ G(m) = G(m')
View Equivalentなら$ w-rのedge graphも必ず同じになるということ．
これはobviousらしい．まあRFが一致 == View Equivalentであり， RFとはつまり$ w-rなので，自明ではある
逆は成り立たない．
その理由は後述されるVersion Orderにある．
以下が実例: スケジュールとグラフ
$ m = w_1(x_1)r_2(x_0)w_1(y_1)r_2(y_1) $ T_1 \to_{wr}T_2 \ T_0 \to_{wr} T_2
$ m' = w_1(x_1)r_2(x_1)w_1(y_1)r_2(y_0) $ T_1 \to_{wr}T_2 \ T_0 \to_{wr} T_2
すなわち$ G(m) = G(m')である．がReads-Fromが異なる．
$ RF(m) = \{(t_0, x, t_2), (t_1, y, t_2) \}
$ RF(m') = \{(t_1, x, t_2), (t_0, y, t_2) \}
このことから分かることがある(以下私流の理解)．
$ w-rの依存関係は二つのTxの間の関係を示すedgeである
Reads-Fromとは，タプルをラベルにした$ w-rのLabeled Edgeである
だから，先ほどの例も，
$ m = w_1(x_1)r_2(x_0)w_1(y_1)r_2(y_1) $ T_1 \to_{y}T_2 \ T_0 \to_{x} T_2
$ m' = w_1(x_1)r_2(x_1)w_1(y_1)r_2(y_0) $ T_1 \to_{x}T_2 \ T_0 \to_{y} T_2
と表記すれば一致しないことは自明．
まあこんな記法を発明したところで何にもならないが...
Version Order
上述した様に$ w-rだけを使ってConflict Graphを描いただけでは，Graphが一致してもReads Fromが一致しない．
言い換えると，$ G(m)を描いても，Reads-Fromが一致する$ G(m')の存在を証明していることにはならない．
Conflict Graphをトポロジカルソート出来ることは，Serial Monoversion Historyが存在することの証明となるが，(当たり前)
このSerial Monoversion HistoryとRFが一致しないのであれば，トポロジカルソートした意味などない．
なので，Conflict GraphだけではMVSRのプロトコルは作れない．
そこでVersion Orderという概念を登場させる．
Definition 5.7 Version Order
if $ xis a data item, a version order for $ xis any nonreflexive and total ordering of all versions of $ xthat are written by operations in $ m. A version order $ << for $ m is the union of all version orders of data items written by operations in $ m.
i.e. $ mの命令順序とは直交する概念Version Order を定義した．これはあるタプルの書込みの全順序である．
$ w_i(x_i) w_j(x_j)だとしても $ T_i << T_jも $ T_j << T_iもありうるということ
更に他のトランザクション$ T_kがいて $ T_i << T_k << T_jとかもありえる.
これでようやくMVSRをGraphで扱う準備ができた．
Multiversion Serialization Graph(MVSG)
Definition 5.8 MVSG
For a given schedule $ mand a version order $ <<, the multiversion serialization graph MVSG(m, <<) of $ m then is the conflict graph $ G(m) = (V,E)with the following edges added for each $ r_k(x_j) and$ w_i(x_i)in CP(m), where $ k, i, j are pairwise distinct: if $ x_i << x_j, then $ (t_i, t_j) \ni E, otherwise $ (t_k, t_i) \ni E
先ほどの議論と変わらず$ w-rをedgeに持つ$ G(m)をまず用意する．
さらにこれに加えて MVSGではVersion Orderを使ってedgeを追加する．
このVersion Orderによるedgeは以下に分岐する
$ r_k(x_j)と$ w_i(x_i)があるとき，
$ x_i << x_j: $ T_i \to T_j
$ x_j << x_i: $ T_k \to T_i
これは $ r-wと$ w-wに見えます！
このedgeを足すことによって，monoversion scheduleでの挙動と同じ制約を課すことができる．
つまりこれは，read the most recent writeした時に生まれるedgeである
ちょっとむずかしいのでここまでの要約
普通に$ w-rのみのConflict Graphをトポロジカルソートできたとしても，MVSRには当たらないことは先程見た．
Graphが同じでも，Reads-Fromが異なっているケースがあったからだ．
Graphが同じでReads-Fromが異なるというのはどういうことか?
つまり，MultiversionからMonoversionにcastするときにReads-Fromが変わっているということである．
これはどう困るか？
GraphをToposortするということは，nodeがトランザクションであることから，Txの全順序を得ることと等しい．
この全順序通りにTxを実行すると，あら不思議Serial Monoversion Historyの出来上がりである．
さらにそこで逆処理をやる．
このSerial Monoversion HistoryをGraphにしてみる．
このGraphは当然，先ほどのMultiversion Historyから生成したGraphと同じであるはず．
だから，Graphが同じならばReads-Fromが同じ，といえれば，GraphでMVSRが検証できる.
なので，同じGraphならReads-Fromも同じ，という特性がどうしても欲しい．
そこで，MVSGではVersion Orderのedgeを追加したことで，この特性を維持した．
さて，ここまで読んで，欠けているピースは一つ:
「なぜVersion Order Edgeがあると同じReads-Fromが維持できるのか?」
そしてその証明が始まる(ここが本章最大の鬼門)
Theorem and Proof
Theorem 5.4
$ m \in MVSR iff there exists a version order $ << such that MVSG(m, <<) is acyclic.
$ mがMVSRなら必ずacyclic MVSGを作れるversion orderが決定できる，ということ．
(if)
Proof (長いのでかいつまみ)
(if) Since MVSG(m, <<) is acyclic, it can be sorted topologically into a serial history $ m'such that $ RF(m) = RF(m')
まず(if)から行く．
MVSGをtopo-sortした際のserial history($ m')ともとのmultiversion history($ m)はReads-Fromが一致する．
いや，これの証明は?
このとき$ m'がmonoversion historyかどうかがまだ分からない．のでこれを考える．
topo-sortした際のhistoryがmultiversion historyなら，MVSRに当てはまらないのでこれは必要．
先ず，考え方としては，version numberをdropできるか?を考える．
i.e. version numberをdropしてもReads-Fromが変わらないか？
version numberをdropすると当然Monoversion Historyになる．
このmonoversion historyと，Reads-Fromが変わらないなら，$ m'はmonoversion history.
では，version orderによってversion numberがdropできるかを考える.
To this end, suppose that $ m' contains operations $ r_k(x_j), $ w_i(x_i).
if $ x_i << x_j, the graph contains version order edge $ t_i \to t_j, which enforces $ T_i <_{m'} T_j.
Conversely, if $ x_j << x_i, then by definition the graph contains edge $ T_k \to T_i enforcing $ T_k <_{m'} T_j.
まず，version orderがあれば，添字が一切繋がっていない二つのreadとwriteのoperationにもedgeが張られることを見た．
Thus, no transaction writes $ x between $ T_i and $ T_k in $ m', so that version numbers can essentially be dropped from $ m'without changing the reads-from relation.
つまり，この一切添字が繋がっていない二つのreadとwriteのoperationの間にwriteがないことを証明できる．
つまり，version numberが無くてもreads from relationが変わらないということだ．
??????????????????????????????????
落ち着いて逆を考えよう
あるreadとwriteの間に他のwriteが入っていることがあり得ると，Reads-From Relationは変わるらしい．
Reads-From Relation自体は$ w-rのことだが，これを維持するには$ r-wを考える必要があるということ?
何で？
(only if)
For a given history $ m and version order $ <<, let $ MV(m, <<) denote the graph that contains version order edges only.
まずVersion Orderで作ったGraphというものを仮定する．$ w-rのedgeのことは忘れる．
Since version order edges depend only on the operations in $ m and the version order, but not on the sequencing of the operations in $ m, we can conclude that if $ m and $ m' are multiversion histories such that $ trans(m) = trans(m'), then $ MV(m, <<) = MV(m', <<)for every version order $ <<.
Version Order edgeは$ mの命令列の順序とは関係なく張られる．
つまり，同じ命令列から構成されるschedule同士があるとして，同じVersion Orderを与えれば同じedgeのGraphになる．
そりゃそうだろ
いや，ここで重要なのは，version numberをdropしてもいい，という話だ．
同じトランザクションの命令列を自由に並び替えると，当然読まれるものは変わってくる．
version numberが変わるからだ．
しかし，それでもVersion Orderが同じなら，張られるedgeは同じである!
Now let $ m \in MVSR, and let $ m' be a serial monoversion history for the same transactions such that $ m \approx_v m'.
$ mがMVSRなら，定義から，$ m'はserial monoversion historyで，$ mとView Equivalentであるとできる．
同じトランザクションの命令列からなるが，serial monoversion historyにした場合のものを$ m'とする，てこと．
By the remark just stated, $ MV(m, <<) = MV(m', <<) for every version order $ <<.
By Theorem 5.3, $ G(m) = G(m').
Clearly, $ G(m') is acyclic(since $ m' is serial), hence so is $ G(m).
m ∈ MVSRなら，View Equivalentなserial monoversion history $ m'がある．
で，View Equivalentなら，生成するconflict Graphも一致する．
で，Graphが一致しているということは，$ G(m)も$ G(m')もacyclicである．
Now define a specific version order $ <<
$ x_i <<_0 x_j :\Leftrightarrow t_i <_{m'} t_j
(i.e., if $ t_i \to t_j is in $ G(m').)
$ G(m)におけるedgeがそのままversion orderと対応する，というversion orderを考えてみる．
i.e. conflict graphにおけるedgeと逆順にversion orderが延びない．
Thus, if $ MV(m', <<_0) is added to $ G(m'), the resulting graph $ MVSG(m', <<_0) remains acyclic,
and the same holds if $ MV(m', <<_0) = MV(m, <<_0) is added to $ G(m) (=G(m')) .
このようなVersion Orderを生成すれば， EdgeをConflict Graphと合体してもMVSGはacyclic.
Version Orderが同じなら同じTxnsは同じMVを持つし，Conflict Graphも同じなので，ここは入れ替え可能．
---
以上が証明となる．しかし，適切なVersion Orderの決定には計算量がかかりすぎる．
なので，次は適当なversion orderを生成するための制約を一つ設けてスケジュールを狭くすることを考える．
Multiversion Conflict Serializability(MCSR)
ここまでのMVSRはこの本の山場かと思うくらいに難解だったが，同様に計算量も多くかかるものだった．
MCSRでは，ここまでの議論を総括しながら理解可能なプロトコルを作れそうなところまで踏み込んでいる．
まず新しいConflictを考える. ここでいうConflictとはCSRのconflictのextended version.
Definition 5.9 Multiversion Conflict
A multiversion conflict in a multiversion schedule $ m is a pair of steps $ r_i(x_j) and $ w_k(x_k) such that $ r_i(x_j) <_m w_k(x_k).
これは先程迄議論していたConflict Graphすなわち $ w-rの依存関係とは全く異なる．
むしろ $ r-wのことを指す．なぜ$ r-wがConflictなのか?
It is easy to see that $ wwpairs on the same data item no longer count as conflicts, as they create different versions and it is up to the read steps to choose the proper version.
$ w-wのconflictはmultiversionには存在しない...今やっとそれを言うのか！
To realize that $ w-rpairs are not really conflicts is a bit more involved.
The essence of a conflict pair $ pqis that we are not allowed to commute $ p with $ q.
conflictというのはそもそも不可逆(交換不可)ということを指すから，$ w-rはconflictじゃない!(えっなんで)
For $ wr pairs, however, commuting the pair so that the read would precede the write is admissible because it restricts the version selection choices for the read that can still render the schedule correct.(i.e. MVSR)
なるほど．readが正しいversionを読めていればいいので，$ w-rのopsの順序は入れ替えても，readのversion numberを弄れば，他の(たとえば，さらに前の)versionを読むことにできる．
そして，その結果として必ずMVSRを維持できる．つまり，前のバージョンを読んだ場合にも，等価な1V-serialが存在する．
So if the resulting schedule, with the read before the write, is MVSR, the original schedule with the $ wr pair would definitely be MVSR as well.
This is the rationale for considering $ wrpairs (on the same data item) as conflict free.
つまり可換なのでconflictではない．
The third remaining type of operation pairs, $ rwpairs, has the opposite effect: by commuting an $ rw pair so that the read would follow the write, we end up with a schedule that has one more choice in selecting an appropriate version for the read step.
$ r-wの入れ替えをやると，そうはいかない．そのwrite versionを正しく読めたread stepは当然居ないはずだ．
So, if we succeed in verifying that the resulting schedule is MVSR, this would still not say anything about the correctness of the original schedule.
なので，この入れ替えをやった結果のscheduleがMVSRだったとしても，もとのscheduleも同じく，という帰結はできない．
より定式化して言って欲しい
Thus, $ rwpairs on the same data item constitute conflicts in a multiversion setting.
なので$ r-wのみがMultiversion Conflictとみなせる.
この$ w-rと$ r-wの非対称性から，Multiversion scheduleのEquivalenceを考える際に単純にconflictを使えばいいとは言えない．
Rather it leads to an asymmetric notion of transforming one schedule into another by means of repeatedly commuting conflict-free operations.
しかし逆に言うと，$ r-w以外のoperationsはconflict-freeであり，入れ替えたとしてもconflictはない．
we do not have a symmetric commutativity relation in our current setting.
If we can eventually produce a serial monoversion history by commuting operations such that we always(i.e. after each transformation step)respect the ordering of $ rwconflict pairs, then we know that a multiversion schedule is guaranteed to be MVSR.
From this argument we can already suspect that this is only sufficient but not necessary condition for membership in MVSR;
this conjecture will soon be confirmed.
すなわち，あるscheduleがあって，そのscheduleから$ r-wの順序関係を維持したまま，他のopsを入れ替えたとき，
serial monoversion scheduleが作れるなら，これはMVSRである!
というのがMVSRの十分条件として考えられる．
MVSRは$ r-wを考慮してない
Definition 5.10 Multiversion Reducibility
A (totally ordered) multiversion history $ m is multiversion reducible if it can be transformed into a serial monoversion history by a finite sequence of transformation steps, each of which exchanges the order of two adjacent steps,
(i.e., steps $ p,qwith $ p < qsuch that $ o<p or $ q<ofor all other steps $ o)
but without reversing the ordering of multiversion conflict(i.e.,$ rw) pair.
ここから，$ mがmultiversion reducibleであれば，MVSRに含まれることがわかる．
このスケジュール空間をMCSRと呼ぶ．$ MCSR \subset MVSR.
で，いよいよGraphを考える．
Definition 5.12 Multiversion Conflict Graph
Let $ m be a multiversion schedule.
The multiversion conflict graph of $ mis a graph that has the transactions of $ mas its nodes and an edge from $ t_i \to t_k if there are steps $ r_i(x_j) and $ w_k(x_k)for the same data item $ xin $ msuch that $ r_i(x_j) <_m w_k(x_k).
なるほど，ここで分かるのは，先ほどのMVSRにおけるVersion Orderの議論と似ているということ．
Version Orderによって，$ r_i(x_j)と$ w_k(x_k)の場合の依存関係は分岐するという話だった．
MCSRとは，Version Orderを$ mにおける命令順序(すなわち先に起こったかどうか)で決定するということだ．
この場合$ T_k \to T_j \to T_iはありえなくなる
すなわち$ T_j \to T_i \to T_kだけがありえる
だからこの分スケジュール空間が狭い
かわりに，Version Orderの決定という非常に難解な処理がすっとばせるので，practicalである!
Limiting the Number of Versions
DBが持てるversionはstorage spaceに依るので有限だよねという話．
そうなるとMVSRを実装すると一口に雖も微妙に制約が変わる．
そこでいくつまでのVersionを保持できるかで$ 1VSRとか$ 2VSRとか$ kVSRというのが出てくる.
$ VSR = 1VSR \subset 2VSR \subset 3VSR \subset ... \subset MVSR
Multiversion Concurrency Control Protocols
ようやく実装の話になる．
MVTO(Multiversion Timestamp Ordering
最初に重要なことを書いてからprotocolの説明をする
$ Gen(MVTO) \subseteq MVSR
$ x_i << x_j \Leftrightarrow ts(t_i) < ts(t_k)
これ特に重要
0. 各Transactionはtimesmtampを開始時に割り振られる．これは単調増加する
1. read時の$ r_i(x)は$ r_i(x_k)に変換される(multiversion cast).
この$ kの決定は，以下:
where $ x_k is the version of $ xthat carries the largest timestamp ≦ $ ts(t_i)
つまり「自分よりTimestampが低い書込みの中で最大のTSを読む」
ここで他の制約がないのもpoint.
Monoversion Timestamp Orderingだと，$ ts(i) < tsof(x)だとabortする
すなわちよくいうMVCCはRead only transactionが全てcommitできるということ．
2. write時の$ w_i(x)は以下のように処理される
(a) 他のread$ r_j(x_k)がいて，かつ$ ts(t_k) < ts(t_i) < ts(t_j)なら，abort
つまり「$ t_jは俺のwriteを読むはずだったのに」という状況
ここで強引に書き込むと，どうなるか?
MVSRの節で見たように，Version Orderによって$ r_j(x_k)と$ w_k(x_k)の間にwriteは無いはず
それがある，という書込みになる
愚直にやってみよう．まず$ G(m)は$ T_j \to T_k
そしてVersion Orderは$ w_k << w_iを採る
TimestampがVersion Orderを決定するというプロトコルなのだ.
Version Orderより，さらにエッジ追加． $ T_j \to T_k
見事にcyclic!
(b) otherwise, $ w_i(x) is transformed into $ w_i(x_i) and executed.
言い換えるとさっきの例でいう$ r_j(x_k)がいるとVersion Order edgeで死ぬので，それがいなければGO
3. CommitはRecoverable かつ Avoid Cascading Abortsでやる
この議論は直交してるので飛ばす
できるということが重要であとはどうでもいい
このプロトコルの課題はお役所的にTxの開始時にtimestampを割り振っているところだろう．
Version Orderをうまいこと決定するのは計算量が多すぎるので，予め決めておく，というプロトコルだ．
この結果として，結果的にMCSR並のスケジュール空間になると思われる．